Search Results

We study the online balanced graph re-partitioning problem (OBGR) which was introduced by Avin, Bienkowski, Loukas, Pacut, and Schmid [Avin et al., 2020] and has recently received significant attention [Pacut et al., 2021; Henzinger et al., 2021; Henzinger et al., 2019; Tobias Forner et al., 2021; Bienkowski et al., 2021] owing to potential applications in large-scale, data-intensive distributed computing. In OBGR, we have a set of 𝓁 clusters, each with k vertices (representing processes or virtual machines), and an online sequence of communication requests, each represented by a pair of vertices. Any request (u,v) incurs unit communication cost if u and v are located in different clusters (and zero otherwise). Any vertex can be migrated from one cluster to another at a migration cost of α ≥ 1. We consider the objective of minimizing the total communication and migration cost in the competitive analysis framework. The only known algorithms (which run in exponential time) include an O(k²𝓁²) competitive [Avin et al., 2020] and an O(k𝓁 2^O(k)) competitive algorithm [Bienkowski et al., 2021]. A lower bound of Ω(k𝓁) is known [Pacut et al., 2021]. In an effort to bridge the gap, recent results have considered beyond worst case analyses including resource augmentation (with augmented cluster capacity [Avin et al., 2020; Henzinger et al., 2019; Henzinger et al., 2021]) and restricted request sequences (the learning model [Henzinger et al., 2019; Henzinger et al., 2021; Pacut et al., 2021]). In this paper, we give deterministic, polynomial-time algorithms for OBGR, which mildly exploit resource augmentation (i.e. augmented cluster capacity of (1+ε) k for arbitrary ε > 0). We improve beyond O(k²𝓁²)-competitiveness (for general 𝓁, k) by first giving a simple algorithm with competitive ratio O(k𝓁²log k). Our main result is an algorithm with a significantly improved competitive ratio of O(k𝓁 log k). At a high level, we achieve this by employing i) an ILP framework to guide the allocation of large components, ii) a simple "any fit" style assignment of small components and iii) a charging argument which allows us to bound the cost of migrations. Like previous work on OBGR, our algorithm and analysis are phase-based, where each phase solves an independent instance of the learning model. Finally, we give an Ω(α k𝓁 log k) lower bound on the total cost incurred by any algorithm for OBGR under the learning model, which quantifies the limitation of a phase-based approach.

This paper initiates the study of the MAX-CUT problem in fully dynamic graphs. Given a graph G = (V,E), we present deterministic fully dynamic distributed and sequential algorithms to maintain a cut on G which always contains at least |E|/2 edges in sublinear update time under edge insertions and deletions to G. Our results include the following deterministic algorithms: i) an O(Δ) worst-case update time sequential algorithm, where Δ denotes the maximum degree of G, ii) the first fully dynamic distributed algorithm taking O(1) rounds and O(Δ) total bits of communication per update in the Massively Parallel Computation (MPC) model with n machines and O(n) words of memory per machine. The aforementioned algorithms require at most one adjustment, that is, a move of one vertex from one side of the cut to the other. We also give the following fully dynamic sequential algorithms: i) a deterministic O(m^{1/2}) amortized update time algorithm where m denotes the maximum number of edges in G during any sequence of updates and, ii) a randomized algorithm which takes Õ(n^{2/3}) worst-case update time when edge updates come from an oblivious adversary.